package com.cn.algorithm.two.recursion;


/*
*  递归：简化思路，拆解问题，求解。
*  核心：1、明确原问题与子问题的关系
*         寻找f(n)与f(n - 1)之间的关系
*         明确递归基（边界条件）
*/
public class Recursion {

    public static void main(String[] args) {
        System.out.println(fib1(5));
        System.out.println(fib2(5));
        System.out.println(fib3(41));
        hanoi(3,"a", "b", " c");
    }


    /*
    * 斐波拉契数列
    */
    public static int fib1(int n) {
        if (n <= 2) {
            return 1;
        }
        return fib1(n - 1) + fib1(n - 2);
    }

    /*
    * 走楼梯：一次只能走一阶或两阶，一共有多少种走法？
    */
    public static int fib2(int n) {
        if (n <= 2) {
            return n;
        }
        return fib1(n - 1) + fib1(n - 2);
    }

    /*
    * 求硬币获取最少数的组合
    */
    public static int fib3(int n) {
        if (n <= 0) {
            return Integer.MAX_VALUE;
        }
        if (n == 1 || n == 5 || n == 20 || n == 25) {
            return 1;
        }
        int min1 = Math.min(fib3(n - 1), fib3(n - 5));
        int min2 = Math.min(fib3(n - 20), fib3(n - 25));
        return Math.min(min1, min2) + 1;
    }

    /*
    * 汉诺塔
    */
    public static void hanoi(int n, String a, String b, String c) {
        if (n <= 1) {
            move(n,a, c);
            return;
        }
        hanoi(n - 1, a, c, b);
        move(n,a, c);
        hanoi(n - 1, b, a, c);
    }

    public static void move(int n, String from, String to) {
        System.out.println("第"+n + "个盘子，从 "+from+"移动到 " + to);
    }
}
